#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
using namespace std;

#if 0
vector<vector<int>> arr;
vector<int> tmp;
void backtracking(int n, int k, int left)
{
	if (tmp.size() == k)
	{
		arr.push_back(tmp);
		return;
	}
	for (int i = left; i <= n; i++)
	{
		tmp.push_back(i);
		backtracking(n, k, i + 1);
		tmp.pop_back();
	}
}
vector<vector<int>> combine(int n, int k) {
	backtracking(n, k, 1);
	for (int i = 0; i<arr.size(); i++)
	{
		for (int j = 0; j < arr[i].size(); j++)
		{
			cout << arr[i][j] << ' ';
		}
		cout << endl;
	}
	return arr;
}
int main()
{
	vector<vector<int>> tmp = combine(4, 2);
	return 0;
}
#endif

vector<vector<int>>TotalVec;
vector<int>Vec;
void backtracking(const int&k, const int&n, int begin, int sum) {
	if (sum == n && Vec.size() == k) {
		TotalVec.push_back(Vec);
		return;
	}
	if (sum > n) return;
	for (int i = begin; i < 10 - (k - Vec.size()) + 1; ++i) {
		sum += i;
		Vec.push_back(i);
		backtracking(k, n, ++begin, sum);
		sum -= i;
		Vec.pop_back();
	}
	return;
}

vector<vector<int>> combinationSum3(int k, int n) {
	TotalVec.clear();
	Vec.clear();
	// int min = 0;
	// for(int i=1;i<=k;++i)
	//     min += i;
	// if(min > n || k > 9) return TotalVec;
	backtracking(k, n, 1, 0);
	return TotalVec;
}
int main()
{
	vector<vector<int>> arr = combinationSum3(2, 18);
	return 0;
}